package algorithm.leetcode.I401to600;

/**
 * 给定两个字符串 s1 和 s2，写一个函数来判断 s2 是否包含 s1 的排列。
 * 酷似Q76
 */

public class Q567 {

    public boolean checkInclusion(String s1, String s2) {
        // s1和s2只包含小写字母
        int[] need = new int[26];
        int s1Len = s1.length();
        for (int i = 0; i < s1.length(); i++) need[s1.charAt(i)-97]++;

        int left = 0, right = 0;
        while (right < s2.length()) {
            int i = s2.charAt(right) - 97;
            if (need[i] > 0) s1Len--;
            need[i]--;

            // s2的left至right已经完全满足s1
            if (s1Len == 0) {
                // 尝试收缩left,while后面的条件如果等于0进入后会++变成1,表示已经不符合当前need数组
                while (left < right && need[s2.charAt(left)-97] < 0) {
                    need[s2.charAt(left)-97]++;
                    left++;
                }
                if (right-left+1 == s1.length()) return true;
                need[s2.charAt(left)-97]++;
                left++;
                s1Len++;
            }
            right++;
        }
        return false;

    }

    public static void main(String[] args) {
        Q567 q567 = new Q567();
        System.out.println(q567.checkInclusion("ab", "eidboooo"));
    }

}
